// ++++++++++++++++++++++++++++++++++++++++
// 《零基础Go语言算法实战》源码
// ++++++++++++++++++++++++++++++++++++++++
// Author:廖显东（ShirDon）
// Blog:https://www.shirdon.com/
// Gitee:https://gitee.com/shirdonl/goAlgorithms.git
// Buy link :https://item.jd.com/14101229.html
// ++++++++++++++++++++++++++++++++++++++++

package main

import "fmt"

var dp [500][500]int16

func minStep(str1, str2 string) int {
	for i, r1 := range str1 {
		for j, r2 := range str2 {
			if r1 == r2 {
				if i != 0 && j != 0 {
					dp[i][j] = dp[i-1][j-1] + 1
				} else {
					dp[i][j] = 1
				}
			} else {
				if i != 0 && j != 0 {
					dp[i][j] = max(dp[i-1][j], dp[i][j-1])
				} else if i != 0 {
					dp[i][j] = dp[i-1][j]
				} else if j != 0 {
					dp[i][j] = dp[i][j-1]
				} else {
					dp[i][j] = 0
				}
			}
		}
	}
	return len(str1) + len(str2) - 2*int(dp[len(str1)-1][len(str2)-1])
}

func max(x, y int16) int16 {
	if x >= y {
		return x
	}
	return y
}

func main() {
	str1 := "ilovegolang"
	str2 := "golang"
	res := minStep(str1, str2)
	fmt.Println(res)
}

//$ go run interview9-3.go
//5
